﻿// 7-11 前序序列创建二叉树 (25 分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//user:LDC
//date:20191106 21:22
//level:7
//key:主要是熟悉了字符串的操作，s.insert（添加位置，个数，字符），还有熟悉了树的建立与遍历；

#include <iostream>
#include<string>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
class TreeNode
{

public:
	char data;
	TreeNode* lchild;
	TreeNode* rchild;
	TreeNode()
	{
		data = 0;
		TreeNode* lchild = NULL;
		TreeNode* rchild = NULL;
		
	}

	void visit(string s,int &i) {//每一次循环中都引用了i来调整读取字符串中的下一个字符
		//cin >> data;
		data = s[i];
		i++;
		if (data != '#') {
			this->lchild = new TreeNode;
			this->rchild = new TreeNode;
		}
	}
	void visit_read() {
		if (data != '#')
		{
			cout << data;
			if (1) { cout << " "; }
		}

	}
	void visit_next_read() {

		cout << data;

	}
	void pretraversal(TreeNode* proot,string s,int &i) {//把字符串传入，是不是引用都无所谓
		if (NULL != proot)
		{
			(proot)->visit(s,i);
			pretraversal(proot->lchild,s,i);
			pretraversal(proot->rchild,s,i);
		}
	}
	void pretraversal_read(TreeNode* proot) {
		if (NULL != proot)
		{
			(proot)->visit_read();
			pretraversal_read(proot->lchild);
			pretraversal_read(proot->rchild);
		}
	}
	void pretraversal_middle_read(TreeNode* proot) {
		if (NULL != proot)
		{
			pretraversal_middle_read(proot->lchild);
			(proot)->visit_read();
			pretraversal_middle_read(proot->rchild);
		}
	}
};





int main() {
	int i = 0;
	string s;
	
	char c;
	while ((c = getchar()) != EOF) 
	{
		getline(cin, s);
		s.insert(0, 1, c);
			i = 0;
			TreeNode* head = new TreeNode;
			head->pretraversal(head, s, i);//建立二叉树

			head->pretraversal_middle_read(head);//遍历二叉树
		
			cout << "\n";
		}
		
	

}